package likou;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/08 08:00
 */
public class _1049 {
    public static void main(String[] args) {
        System.out.println(lastStoneWeightII3(new int[]{
                31, 26, 33, 21, 40
        }));
    }
    public static int lastStoneWeightII(int[] stones) {
        List<Integer> res = new ArrayList<>(stones.length);
        List<Integer> temp = new ArrayList<>();
        for (int stone : stones) {
            res.add(stone);
        }
        while (res.size()!=1){
            Collections.sort(res);
            int left = 0,right = res.size()-1;
            while (left<right){
                temp.add(res.get(right)-res.get(left));
                left++;
                right--;
            }
            if (left==right){
                temp.add(res.get(right));
            }
            res = temp;
            temp = new ArrayList<>();
        }
        return res.get(0);
    }

    public static int lastStoneWeightII3(int[] ss) {
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[] f = new int[t + 1];
        for (int i = 1; i <= n; i++) {
            int x = ss[i - 1];
            for (int j = t; j >= x; j--) {
                f[j] = Math.max(f[j], f[j - x] + x);
            }
            System.out.println(Arrays.toString(f));
        }
        return Math.abs(sum - f[t] - f[t]);
    }


    public int lastStoneWeightII2(int[] stones) {
        int sum=0;
        for(int st:stones)
            sum+=st;
        for(int i=(sum>>1);;i--){
            if(helper(stones,0,0,i))
                return sum-2*i;
        }
    }

    boolean helper(int[] nums,int idx,int sum,int target){
        if(sum==target)
            return true;
        if(sum>target)
            return false;
        if(idx==nums.length)
            return false;
        return helper(nums,idx+1,sum+nums[idx],target)
                ||helper(nums,idx+1,sum,target);
    }
}
